#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include "gc.h"
#include "mem.h"
#include "redexceptionobject.h"

#define ptradd(p, n, t)		(t *)(((uintptr_t)(p)) + (n))

static const int CLASS_SIZE[] =
{
	[mc_32]		= 32,
	[mc_64]		= 64,
	[mc_80]		= 80,
	[mc_96]		= 96,
	[mc_144]	= 144,
	[mc_256]	= 256,
	[mc_512]	= 512,
	[mc_4k]		= 4096,
	[mc_16k]	= 16384,
	[mc_64k]	= 65536,
	[mc_256k]	= 262144,
	[mc_1M]		= 1048576,
	[mc_4M]		= 4194304,
	[mc_16M]	= 16777216,
};

static const int CLASS_CHUNKS[] =
{
	[mc_32]		= 128,
	[mc_64]		= 128,
	[mc_80]		= 128,
	[mc_96]		= 128,
	[mc_144]	= 128,
	[mc_256]	= 64,
	[mc_512]	= 64,
	[mc_4k]		= 64,
	[mc_16k]	= 32,
	[mc_64k]	= 32,
	[mc_256k]	= 16,
	[mc_1M]		= 16,
	[mc_4M]		= 8,
	[mc_16M]	= 8,
};

size_t RedMem_MaxMemory = MEM_MAX_MEMORY;
RedMemoryState Red_MemoryState = { 0, 0, {{{ 0 }}} };

static inline RedMemoryClass size_to_class(size_t size)
{
#ifndef DEBUG
	for (RedMemoryClass class = RedMemoryClassStart; class < RedMemoryClassCount; class++)
		if (size <= CLASS_SIZE[class])
			return class;
#endif

	return mc_unmanaged;
}

static inline void node_init(RedMemoryNode *node)
{
	node->prev = node;
	node->next = node;
}

static inline void node_remove(RedMemoryNode *node)
{
	node->prev->next = node->next;
	node->next->prev = node->prev;
}

static inline void node_append(RedMemoryNode *list, RedMemoryNode *node)
{
	node->next = list;
	node->prev = list->prev;
	list->prev->next = node;
	list->prev = node;
}

static inline void pool_init(RedMemoryPool *node)
{
	node->prev = node;
	node->next = node;
}

static inline void pool_remove(RedMemoryPool *node)
{
	node->prev->next = node->next;
	node->next->prev = node->prev;
}

static inline void pool_append(RedMemoryPool *list, RedMemoryPool *node)
{
	node->next = list;
	node->prev = list->prev;
	list->prev->next = node;
	list->prev = node;
}

static void release_pool(RedMemoryPool *pool)
{
	/* get memory descriptor by class */
	size_t stride = sizeof(RedMemoryNode) + CLASS_SIZE[pool->class];
	RedMemoryDesc *desc = &(Red_MemoryState.classes[pool->class]);

	/* update memory counter */
	desc->available -= CLASS_CHUNKS[pool->class];

	/* remove all chunks from free list */
	for (int i = 0; i < CLASS_CHUNKS[pool->class]; i++)
		node_remove(ptradd(pool + 1, stride * i, RedMemoryNode));

	/* remove pool from list and release it's memory */
	pool_remove(pool);
	OS_FREE(pool);
}

static char allocate_pool(RedMemoryClass class)
{
	/* allocate all memory in once */
	size_t stride = sizeof(RedMemoryNode) + CLASS_SIZE[class];
	RedMemoryPool *result = OS_MALLOC(sizeof(RedMemoryPool) + stride * CLASS_CHUNKS[class]);

	/* we cannot even allocate memory, it's fatal */
	if (!result)
		return 0;

	/* get memory descriptor by class */
	RedMemoryDesc *desc = &(Red_MemoryState.classes[class]);

	/* initialize pool */
	result->usage = 0;
	result->class = class;

	/* split memory into chunks and apped into free list */
	for (int i = 0; i < CLASS_CHUNKS[class]; i++)
	{
		RedMemoryNode *node = ptradd(result + 1, stride * i, RedMemoryNode);

		/* initialize memory node */
		node->pool = result;
		node->size = CLASS_SIZE[class];
		node->class = class;

		/* append to free list */
		node_append(&(desc->free), node);
	}

	/* append to the classified pool list */
	pool_append(&(desc->pool), result);

	/* update usage info */
	desc->available += CLASS_CHUNKS[class];
	return 1;
}

static void release_node(RedMemoryNode *node)
{
	/* get memory descriptor by class */
	RedMemoryDesc *desc = &(Red_MemoryState.classes[node->class]);

	/* enter critical section */
	RedSpin_Acquire(&(desc->spin_node));

	/* detach it and add to free list */
	node_remove(node);
	node_append(&(desc->free), node);

	/* update counters */
	desc->allocated--;
	desc->available++;

	/* leave critical section */
	RedSpin_Release(&(desc->spin_node));

	/* release empty pools */
	if (ATOMIC_DEC(node->pool->usage) == 0)
	{
		RedMutex_Acquire(&(desc->mutex_pool));
		release_pool(node->pool);
		RedMutex_Release(&(desc->mutex_pool));
	}
}

static RedMemoryNode *allocate_node(RedMemoryClass class)
{
	/* get memory descriptor by class */
	RedMemoryDesc *desc = &(Red_MemoryState.classes[class]);

	/* no available chunks in this class, create a pool */
	if (!(desc->available))
	{
		char result = 1;

		/* enter critical section */
		RedMutex_Acquire(&(desc->mutex_pool));

		/* still not available, create a new pool */
		if (!(desc->available))
			result = allocate_pool(class);

		/* leave critical section */
		RedMutex_Release(&(desc->mutex_pool));

		/* failed to create a new pool */
		if (!result)
			return NULL;
	}

	/* enter critical section */
	RedSpin_Acquire(&(desc->spin_node));

	/* update counters first */
	desc->available--;
	desc->allocated++;

	/* grab a chunk from free list */
	RedMemoryNode *node = desc->free.next;

	/* detach it and add to using list */
	node_remove(node);
	node_append(&(desc->using), node);

	/* leave critical section */
	RedSpin_Release(&(desc->spin_node));

	/* update pool usage */
	ATOMIC_INC(node->pool->usage);
	return node;
}

void Red_FreeMemoryPool(void)
{
	for (RedMemoryClass class = RedMemoryClassStart; class < RedMemoryClassCount; class++)
	{
		/* get memory descriptor by class */
		RedMemoryDesc *desc = &(Red_MemoryState.classes[class]);

		/* release all pools in this class */
		while (desc->pool.next != &(desc->pool))
			release_pool(desc->pool.next);

		/* release the pool mutex */
		RedMutex_Free(&(desc->mutex_pool));
	}
}

void Red_InitMemoryPool(void)
{
	for (RedMemoryClass class = RedMemoryClassStart; class < RedMemoryClassCount; class++)
	{
		Red_MemoryState.classes[class].spin_node = 0;
		Red_MemoryState.classes[class].allocated = 0;
		Red_MemoryState.classes[class].available = 0;
		pool_init(&(Red_MemoryState.classes[class].pool));
		node_init(&(Red_MemoryState.classes[class].free));
		node_init(&(Red_MemoryState.classes[class].using));
		RedMutex_Init(&(Red_MemoryState.classes[class].mutex_pool));
	}
}

void RedMem_Free(void *ptr)
{
	if (ptr)
	{
		/* convert to memory node */
		RedMemoryNode *node = ((RedMemoryNode *)ptr) - 1;

		/* update usage statistics */
		Red_MemoryState.malloc -= node->size;

		/* large blocks are not managed by Red Memory Manager */
		if (node->class == mc_unmanaged)
			OS_FREE(node);
		else
			release_node(node);
	}
}

static inline void *retry_with_gc(size_t size)
{
	/* perform an emergency garbage collection */
	if (RedObject_GC_Collect())
		return RedMem_Alloc(size);

	/* if nothing collected, we cannot allocate memory now */
	RedException_Throw(&RedExc_MemoryError);
	return NULL;
}

void *RedMem_Alloc(size_t size)
{
	/* limit the memory usage */
	if (Red_MemoryState.malloc + size > RedMem_MaxMemory)
		return retry_with_gc(size);

	/* convert size to memory class */
	RedMemoryClass class = size_to_class(size);

	/* large blocks are not managed by Red Memory Manager */
	if (class != mc_unmanaged)
	{
		/* allocate from pool */
		RedMemoryNode *node = allocate_node(class);

		/* failed to allocate memory, retry after GC */
		if (!node)
			return retry_with_gc(size);

		/* update usage statistics */
		Red_MemoryState.malloc += node->size;
		return (void *)(node + 1);
	}

	/* create a unmanaged node */
	RedMemoryNode *node = OS_MALLOC(sizeof(RedMemoryNode) + size);

	/* failed to allocate memory, retry after GC */
	if (!node)
		return retry_with_gc(size);

	/* initialize this node */
	node->size = size;
	node->class = mc_unmanaged;

	/* update usage statistics */
	Red_MemoryState.malloc += size;
	return (void *)(node + 1);
}

void *RedMem_Resize(void *ptr, size_t size)
{
	if (!ptr)
		return RedMem_Alloc(size);

	/* convert to memory node */
	RedMemoryNode *node = ((RedMemoryNode *)ptr) - 1;

	/* shrinking is bypassed */
	if (node->size >= size)
		return ptr;

	/* simply free and allocate a new one */
	RedMem_Free(ptr);
	return RedMem_Alloc(size);
}

void *RedMem_Realloc(void *ptr, size_t size)
{
	if (!ptr)
		return RedMem_Alloc(size);

	/* convert to memory node */
	RedMemoryNode *node = ((RedMemoryNode *)ptr) - 1;

	/* shrinking is bypassed */
	if (node->size >= size)
		return ptr;

	/* simply free and allocate a new one */
	void *new = RedMem_Alloc(size);

	/* failed to allocate memory */
	if (!new)
	{
		RedMem_Free(ptr);
		return NULL;
	}

	/* copy data */
	memcpy(new, ptr, node->size);
	RedMem_Free(ptr);
	return new;
}
